package com.cty._04_Optimization._51_InversePairs;

/**
 * @Auther: cty
 * @Date: 2020/7/20 12:12
 * @Description: 面试题51：数组中的逆序对
 * 题目：在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组
 * 成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
 * @version: 1.0
 */
public class InversePairs {

    /**
     * 归并排序实现
     * 时间复杂度  N*logN
     * 空间复杂度  N
     * @param array
     * @return
     */
    public static int InversePairs(int[] array){
        if(array==null || array.length==0)
            return 0;

        int [] workSpace = new int[array.length];
        return recInversePairs(array,workSpace,0,array.length-1);
    }

    private static int recInversePairs(int[] array, int[] workSpace, int lowerBound, int upperBound){
        if(lowerBound == upperBound)
            return 0;

        int median = (upperBound+lowerBound)>>1;
        int left = recInversePairs(array,workSpace,lowerBound,median);
        int right = recInversePairs(array,workSpace,median+1,upperBound);
        int count =merge(array,workSpace,lowerBound,median,upperBound);

        return left + right + count;
    }

    private static int merge(int[] array, int[] workSpace,int lowerBound, int median, int upperBound){
        int lowerMin = lowerBound;
        int lowerPtr = median;
        int upperMin = median + 1;
        int upperPtr = upperBound;
        int index = upperBound - lowerBound;
        int count = 0;

        while(lowerPtr>=lowerMin && upperPtr>=upperMin){
            if(array[lowerPtr] > array[upperPtr]) {
                workSpace[index--] = array[lowerPtr--];
                count += upperPtr - upperMin + 1;
            }
            else
                workSpace[index--] = array[upperPtr--];
        }

        while(lowerPtr>=lowerMin)
            workSpace[index--] = array[lowerPtr--];
        while(upperPtr>=upperMin)
            workSpace[index--] = array[upperPtr--];

        for(int i=0; i<=upperBound-lowerBound; i++)
            array[lowerBound+i] = workSpace[i];

        return count;
    }  // end merge()

}  // end class
